leetcode 75 颜色分类

这个其实是简化版本的快排，相当于只有三种元素，一个待定区，一个大于待定区的数，一个小于待定区的数。

题目

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

思路

题目还是很好理解的，就是把0全部放在前面，把1全部放在中间，剩下的2全部放在后面，依然是双指针解决问题，我们利用一个left（初始指向索引0）和一个right（初始指向索引nums.size()-1）分别指向应该放0元素的区域和应该放2元素的区域。然后开始遍历元素，若当前元素为0，我们将其与left指向元素交换位置，然后left向前移动一个位置，若为1，我们则不用管，因为0会被放到前面，2会被放到最后面，在这个过程当中，1就会移动到中央区域，如果检测到是2，那么将其与right位置的元素交换位置，然后right向前移动一位，注意，此时因为i的元素变成了由原来的right移动而来的元素，所以需要对其重新进行判断，所以i–可以和for循环的i++抵消，前面等于0不做此运算，是因为在i的前面只会有元素0和元素1，所以移动此时的i应该为1或者0，位置是正确的，最后当i>=right时,可以终止循环了，因为i之后的元素全部为2，不需要再进行移动。

code

void sortColors(vector<int>& nums) {
    int left=0;
    int right=nums.size()-1;
    for(int i=0;i<nums.size();i++)
    {
        if(nums[i]==0)
        {
            swap(nums[i],nums[left]);
            left++;
        }
        else if(nums[i]==2)
        {
            swap(nums[i],nums[right]);
            right--;
            i--;
        }
        if(i>=right)
            break;
    }


}